原文題目

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

題目摘要

1. 問題描述：給定一個字串 s 和一個字典 wordDict（包含若干個字串），判斷字串 s 是否可以被分割成一個或多個字典中的單詞，且單詞可以重複使用。
2. 輸入：一個字串 s，例如 "applepie"、一個字典 wordDict，例如 ["apple", "pie"]。
3. 輸出：如果字串 s 可以被分割成字典中的單詞，返回 true。否則，返回 false。

Example 1:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

解題思路

1. 使用動態規劃：

   設立一個boolean陣列 dp，其中 dp[i] 表示字串 s[0:i] 是否可以被分割成字典中的單詞。

2. 初始化：

   dp[0] 設為 true，因為空字串 s[0:0] 被視為可以被分割（即不需要任何單詞）。

3. 外層循環：

   遍歷字串 s 的每個位置 i（從 1 到 s.length()），檢查字串 s[0:i] 是否可以被分割成字典中的單詞。

4. 內層循環：

   • 對於每個位置 i，遍歷從 0 到 i 的所有可能的分割點 j。
   • 將字串 s[0:j] 及 s[j:i] 進行比較：如果 dp[j] 為 true（即 s[0:j] 可以被分割），並且 s[j:i] 在字典 wordDict 中，則 s[0:i] 也可以被分割。

5. 更新 dp 陣列：

   • 如果上述條件滿足，則將 dp[i] 設為 true，表示字串 s[0:i] 可以被分割成字典中的單詞。
   • 只要找到有效的分割點，直接退出內部循環以提高效率。

6. 回傳結果：

   • 最終回傳 dp[s.length()]，表示整個字串 s 是否可以被分割成字典中的單詞。

程式碼

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        //創建一個boolean陣列dp，用於記錄子字串是否可以被分割
        //dp[i]表示字串s的前i個字符是否可以被字典中的單詞分割
        boolean[] dp = new boolean[s.length() + 1];
        // 初始化dp[0]為true，因為空字串被視為可分割
        dp[0] = true;
        //dp[0]已經初始化為true，故i從1開始走遍整個s
        for (int i = 1; i <= s.length(); i++) {
            //j用於檢查s從j到i是否可以作為一個子字串出現在wordDict中
            for (int j = 0; j < i; j++) {
                //檢查(1)dp[j]是否為true(2)子字串s[j:i]是否在wordDict中
                //若皆為true則表示s[0:j]可分割且s[j:i]在字典中
                if (wordDict.contains(s.substring(j, i)) && dp[j]) {
                    //符合條件則設置dp[i]為true
                    dp[i] = true;
                    //找到有效的分割後，跳出內層迴圈
                    break;
                }
            }
        }
        //回傳dp[s.length()]，即整個字串是否可以被分割
        return dp[s.length()];
    }
}

結論： 在這題「 Word Break 」教會我們如何利用動態規劃來拆解複雜問題。就像在生活中，有時候我們面對一個大任務，會將它分解成更小、更易處理的部分。這樣可以一步步檢查，逐步解決，最終達成目標。這個方法不僅在編程中有效，還能應用到學習新技能或完成日常工作中。掌握了這種思維方式，你會發現解決問題變得更加有條理和高效。